Paper 2021/807

Non-Interactive Batch Arguments for NP from Standard Assumptions

Arka Rai Choudhuri, Abhishek Jain, and Zhengzhong Jin

Abstract

We study the problem of designing *non-interactive batch arguments* for $\mathsf{NP}$. Such an argument system allows an efficient prover to prove multiple $\mathsf{NP}$ statements, with size smaller than the combined witness length. We provide the first construction of such an argument system for $\mathsf{NP}$ in the common reference string model based on standard cryptographic assumptions. Prior works either require non-standard assumptions (or the random oracle model) or can only support private verification. At the heart of our result is a new *dual mode* interactive batch argument system for $\mathsf{NP}$. We show how to apply the correlation-intractability framework for Fiat-Shamir -- that has primarily been applied to proof systems -- to such interactive arguments.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in CRYPTO 2021
Keywords
Batch argumentsFiat-Shamir Transformation
Contact author(s)
achoud @ cs jhu edu
abhishek @ cs jhu edu
zjin12 @ jhu edu
History
2021-06-16: received
Short URL
https://ia.cr/2021/807
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/807,
      author = {Arka Rai Choudhuri and Abhishek Jain and Zhengzhong Jin},
      title = {Non-Interactive Batch Arguments for {NP} from Standard Assumptions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/807},
      year = {2021},
      url = {https://eprint.iacr.org/2021/807}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.